/**
 * A*原理
 * 1、首先把start放入closeList中，start作为当前点。
 * 2、然后从当前点开始辐射找其它路径点P。
 * 3、P如果已经在closeList中则不管他；P如果已经在openList中则如果当前移动量更小，更新它的移动量和前继；都不在的话计算移动量和前继添加到openList中。
 * 4、从openList中找到合值最小的点添加到closeList中，并以此作为当前点，重复2和3，直到寻找到终点。
 */

interface IPoint {
    x: number;
    y: number
}

export enum Mode {
    Four = 0,
    Eight = 1,
    Six = 2
}

//曼哈顿估价法
function manhattan(start: IPoint, end: IPoint) {
    return Math.abs(start.x - end.x) + Math.abs(start.y - end.y);
}

class Grid {
    static create(x: number, y: number, cost: number) {
        return new Grid(x, y, cost);
    }
    constructor(x: number, y: number, cost: number) {
        cost = Math.floor(cost);
        if (cost < 1) cost = 1;
        this.cost = cost;

        this.point.x = x;
        this.point.y = y;
    }
    clear() {
        this.G = -1;
        this.H = -1;
        this.last = null;
        this.isObstacle = false;
    }
    // 坐标
    point: IPoint = { x: 0, y: 0 }
    /**
     * 移动代价
     */
    cost: number = 1;

    /**
     * 是否是障碍物
     */
    isObstacle = false;
    /**
     * 前继
     */
    last: Grid | null = null;
    /**
     * 当前移动量
     */
    G: number = -1;
    /**
     * 剩余预估量
     */
    H: number = -1;
    /**
     * G+H合值
     */
    get F(): number { return this.G + this.H };

}

export class AStar {
    // 地图
    private map: Grid[][] = [];
    // 行数
    private rowCount: number = 0;
    // 列数
    private colCount: number = 0;

    // open和close列表
    private openList: Grid[] = [];
    private closeList: Grid[] = [];

    /**
     * 
     * @param row 行数
     * @param col 列数
     * @param handle 可根据坐标人为返回当前grid的移动代价值(默认是1)
     */
    constructor(row: number, col: number, handle?: (row: number, col: number) => number) {
        this.rowCount = row;
        this.colCount = col;

        // 初始化地图
        for (let i = 0; i < row; i++) {
            let array: Grid[] = Array(col);
            if (handle) {
                for (let j = 0; j < array.length; j++) {
                    array[j] = Grid.create(i, j, handle(i, j));
                }
            } else {
                for (let j = 0; j < array.length; j++) {
                    array[j] = Grid.create(i, j, 1);
                }
            }
            this.map.push(array);
        }
    }

    /**
     * 添加障碍物
     */
    addObstacle(points: IPoint[] | IPoint) {
        if (points instanceof Array) {
            for (let i = 0, point: IPoint = null!; i < points.length; i++) {
                point = points[i];
                this.map[point.x][point.y].isObstacle = true;
            }
        } else {
            this.map[points.x][points.y].isObstacle = true;
        }
    }

    /**
     * 移除障碍物
     */
    delObstacle(points: IPoint[] | IPoint) {
        if (points instanceof Array) {
            for (let i = 0, point: IPoint = null!; i < points.length; i++) {
                point = points[i];
                this.map[point.x][point.y].isObstacle = false;
            }
        } else {
            this.map[points.x][points.y].isObstacle = false;
        }
    }

    /**
     * 获得路径
     */
    getRoute(start: IPoint, end: IPoint, mode: Mode) {
        if (this.map[start.x][start.y].isObstacle) {
            console.error('起点不能是障碍物');
            return [];
        }

        if (this.map[end.x][end.y].isObstacle) {
            console.error('终点不能是障碍物');
            return [];
        }

        if (start.x == end.x && start.y == end.y) {
            console.error('起点和终点不能相同');
            return [];
        }

        this.openList.forEach(this.clearGrid);
        this.closeList.forEach(this.clearGrid);
        this.openList.length = 0;
        this.closeList.length = 0;

        const head = this.map[start.x][start.y];

        let grid: Grid | null = head;
        while (grid) {
            this.addToCloseList(grid);
            // 寻找不在closeList的邻居Gride
            let grids = this.getNeighbor(grid, mode).filter(_grid => !this.isInCloseList(_grid));
            // 更新Gride属性
            this.updateGrids(grids, grid, end);
            // 添加到openList
            this.addToOpenList(grids);
            // 过的最小F值的Gride
            grid = this.getOpenListMinF();
            // 是终点
            if (grid && grid.point.x === end.x && grid.point.y === end.y) {
                return this.getRouteByGrid(grid);
            }
        }

        return [];
    }

    private clearGrid(grid: Grid,) {
        grid.clear();
    }

    private getRouteByGrid(grid: Grid, route?: IPoint[]) {
        route = route || [];

        if (grid.last) {
            this.getRouteByGrid(grid.last, route);
        }
        route.push(grid.point);
        return route;
    }

    private updateGrids(grids: Grid[] | Grid, last: Grid, end: IPoint) {
        if (grids instanceof Array) {
            grids.forEach(grid => this.updateGrids(grid, last, end));
        } else {
            const G = last.G + grids.cost;

            if (grids.G === -1) {
                grids.H = manhattan(grids.point, end);
                grids.G = G;
                grids.last = last;
            } else if (grids.G > G) {
                grids.G = G;
                grids.last = last;
            } else if (grids.G === G) {
                // 这里的情况是出现多条可选路
                // 不处理的话也没影响，默认走第一次计算的路径
                // 加入随机函数的话，每次走的路径可能不同
                // if (Math.random() > 0.5) {
                //     grids.G = G;
                //     grids.last = last;
                // }
            }
        }
    }

    private addToOpenList(grids: Grid[] | Grid) {
        if (grids instanceof Array) {
            grids.forEach(grid => this.addToOpenList(grid));
            return;
        }

        if (this.openList.length === 0) {
            this.openList.push(grids);
            return;
        }

        const isin = this.isInOpenList(grids);
        if (isin) {
            if (grids.F <= this.openList[0].F) {
                this.openList.splice(isin - 1, 1);
                this.openList.unshift(grids);
            }
            return;
        }

        if (grids.F <= this.openList[0].F) {
            this.openList.unshift(grids);
        } else {
            this.openList.push(grids);
        }
    }

    private addToCloseList(grid: Grid) {
        if (this.isInCloseList(grid)) return;
        this.closeList.push(grid);
    }

    private getOpenListMinF() {
        return this.openList.shift() || null;;
    }

    private isInOpenList(grid: Grid) {
        for (let index = 0; index < this.openList.length; index++) {
            if (this.openList[index] === grid) return index + 1;
        }
        return 0;
    }

    private isInCloseList(grid: Grid) {
        for (let index = 0; index < this.closeList.length; index++) {
            if (this.closeList[index] === grid) return index + 1;
        }
        return 0;
    }

    /**
     * 寻找邻居(会排除障碍物)
     */
    private getNeighbor(grid: Grid, mode: Mode): Grid[] {
        const x = grid.point.x;
        const y = grid.point.y;

        const minX = 0;
        const minY = 0;
        const maxX = this.colCount - 1;
        const maxY = this.rowCount - 1;

        const result: Grid[] = [];

        if (mode === Mode.Four || mode === Mode.Eight) {
            // 下
            if (y > minY) result.push(this.map[x][y - 1]);
            // 左
            if (x > minX) result.push(this.map[x - 1][y]);
            // 上
            if (x < maxX) result.push(this.map[x + 1][y]);
            // 右
            if (y < maxY) result.push(this.map[x][y + 1]);

            // 斜向要避免穿墙
            if (mode === Mode.Eight) {
                //左下
                if (x > minX && y > minY && (!this.map[x - 1][y].isObstacle && !this.map[x][y - 1].isObstacle))
                    result.push(this.map[x - 1][y - 1]);
                // 左上
                if (x > minX && y < maxY && (!this.map[x - 1][y].isObstacle && !this.map[x + 1][y].isObstacle))
                    result.push(this.map[x - 1][y + 1]);
                // 右上
                if (x < maxX && y < maxY && (!this.map[x][y + 1].isObstacle && !this.map[x + 1][y].isObstacle))
                    result.push(this.map[x + 1][y + 1]);
                // 右下
                if (x < maxX && y > minY && (!this.map[x][y + 1].isObstacle && !this.map[x][y - 1].isObstacle))
                    result.push(this.map[x + 1][y - 1]);
            }
        } else {
            // 六个单元的分布。
            // 对单行（i行）的单元而言，单元(i,j)周边的六个是(i-1,j)、(i-1,j+1)、(i,j-1)、(i,j+1)、(i+1,j)、(i+1,j+1)
            // 对双行（i行）的单元而言，单元(i,j)周边的六个是(i-1,j-1)、(i-1,j)、(i,j-1)、(i,j+1)、(i+1,j-1)、(i+1,j)
            // 这样一来，其他的都可以套用A*了
            const xnum = x / 2;
            if (xnum === Math.floor(xnum)) {
                // 双行
                if (x > minX && y > minY) result.push(this.map[x - 1][y - 1]);
                if (x > minX) result.push(this.map[x - 1][y]);
                if (y > minY) result.push(this.map[x][y - 1]);
                if (y < maxY) result.push(this.map[x][y + 1]);
                if (x < maxX && y > minY) result.push(this.map[x + 1][y - 1]);
                if (x < maxX) result.push(this.map[x + 1][y]);
            } else {
                // 单行
                if (x > minX) result.push(this.map[x - 1][y]);
                if (x > minX && y < maxY) result.push(this.map[x - 1][y + 1]);
                if (y > minY) result.push(this.map[x][y - 1]);
                if (y < maxY) result.push(this.map[x][y + 1]);
                if (x < maxX) result.push(this.map[x + 1][y]);
                if (x < maxX && y < maxY) result.push(this.map[x + 1][y + 1]);
            }
        }

        return result.filter(function (grid) {
            return !grid.isObstacle;
        });
    }
}